home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / merge.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-13  |  6.1 KB  |  269 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. bool mergedebug;                        /* ? */
  5.  
  6. /*
  7.  * ================
  8.  * CheckColinear
  9.  * 
  10.  * ================
  11.  */
  12. void CheckColinear(register struct visfacet *f)
  13. {
  14.   int i, j;
  15.   vec3_t v1, v2;
  16.  
  17.   for (i = 0; i < f->numpoints; i++) {
  18.     /*
  19.      * skip the point if the vector from the previous point is the same
  20.      * as the vector to the next point
  21.      */
  22.     j = (i - 1 < 0) ? f->numpoints - 1 : i - 1;
  23.     VectorSubtract(f->pts[i], f->pts[j], v1);
  24.     VectorNormalize(v1);
  25.  
  26.     j = (i + 1 == f->numpoints) ? 0 : i + 1;
  27.     VectorSubtract(f->pts[j], f->pts[i], v2);
  28.     VectorNormalize(v2);
  29.  
  30.     if (VectorCompare(v1, v2))
  31.       Error("Colinear edge");
  32.   }
  33.  
  34. }
  35.  
  36. /*
  37.  * =============
  38.  * TryMerge
  39.  * 
  40.  * If two polygons share a common edge and the edges that meet at the
  41.  * common points are both inside the other polygons, merge them
  42.  * 
  43.  * Returns NULL if the faces couldn't be merged, or the new face.
  44.  * The originals will NOT be freed.
  45.  * =============
  46.  */
  47. struct visfacet *TryMerge(__memBase, register struct visfacet *f1, register struct visfacet *f2)
  48. {
  49.   vec_t *p1, *p2, *p3, *p4, *back;
  50.   struct visfacet *newf;
  51.   int i, j, k, l;
  52.   vec3_t normal, delta, planenormal;
  53.   vec_t dot;
  54.   struct plane *plane;
  55.   bool keep1, keep2;
  56.  
  57.   if (f1->numpoints == -1 || f2->numpoints == -1)
  58.     return NULL;
  59.   if (f1->planeside != f2->planeside)
  60.     return NULL;
  61.   if (f1->texturenum != f2->texturenum)
  62.     return NULL;
  63.   if (f1->contents[0] != f2->contents[0])
  64.     return NULL;
  65.   if (f1->contents[1] != f2->contents[1])
  66.     return NULL;
  67.  
  68.   /* find a common edge */
  69.   p1 = p2 = NULL;                        /* stop compiler warning */
  70.   j = 0;
  71.  
  72.   for (i = 0; i < f1->numpoints; i++) {
  73.     p1 = f1->pts[i];
  74.     p2 = f1->pts[(i + 1) % f1->numpoints];
  75.     for (j = 0; j < f2->numpoints; j++) {
  76.       p3 = f2->pts[j];
  77.       p4 = f2->pts[(j + 1) % f2->numpoints];
  78.       for (k = 0; k < 3; k++) {
  79.     if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
  80.       break;
  81.     if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
  82.       break;
  83.       }
  84.       if (k == 3)
  85.     break;
  86.     }
  87.     if (j < f2->numpoints)
  88.       break;
  89.   }
  90.  
  91.   if (i == f1->numpoints)
  92.     return NULL;                        /* no matching edges */
  93.  
  94.   /*
  95.    * check slope of connected lines
  96.    * if the slopes are colinear, the point can be removed
  97.    */
  98. #ifdef EXHAUSIVE_CHECK
  99.   if (f1->planenum >= bspMem->numbrushplanes || f1->planenum < 0)
  100.     Error("looking for nonexisting plane %d\n", f1->planenum);
  101. #endif
  102.   plane = &bspMem->brushplanes[f1->planenum];
  103.   VectorCopy(plane->normal, planenormal);
  104.   if (f1->planeside)
  105.     VectorNegate(planenormal);
  106.  
  107.   back = f1->pts[(i + f1->numpoints - 1) % f1->numpoints];
  108.   VectorSubtract(p1, back, delta);
  109.   CrossProduct(planenormal, delta, normal);
  110.   VectorNormalize(normal);
  111.  
  112.   back = f2->pts[(j + 2) % f2->numpoints];
  113.   VectorSubtract(back, p1, delta);
  114.   dot = DotProduct(delta, normal);
  115.   if (dot > CONTINUOUS_EPSILON)
  116.     return NULL;                        /* not a convex polygon */
  117.  
  118.   keep1 = dot < -CONTINUOUS_EPSILON;
  119.  
  120.   back = f1->pts[(i + 2) % f1->numpoints];
  121.   VectorSubtract(back, p2, delta);
  122.   CrossProduct(planenormal, delta, normal);
  123.   VectorNormalize(normal);
  124.  
  125.   back = f2->pts[(j + f2->numpoints - 1) % f2->numpoints];
  126.   VectorSubtract(back, p2, delta);
  127.   dot = DotProduct(delta, normal);
  128.   if (dot > CONTINUOUS_EPSILON)
  129.     return NULL;                        /* not a convex polygon */
  130.  
  131.   keep2 = dot < -CONTINUOUS_EPSILON;
  132.  
  133.   /* build the new polygon */
  134.   if (f1->numpoints + f2->numpoints > MAXEDGES) {
  135. /*              Error ("TryMerge: too many edges!"); */
  136.     return NULL;
  137.   }
  138.  
  139.   newf = NewFaceFromFace(f1, MAXEDGES);
  140.  
  141.   /* copy first polygon */
  142.   for (k = (i + 1) % f1->numpoints; k != i; k = (k + 1) % f1->numpoints) {
  143.     if (k == (i + 1) % f1->numpoints && !keep2)
  144.       continue;
  145.  
  146.     VectorCopy(f1->pts[k], newf->pts[newf->numpoints]);
  147.     newf->numpoints++;
  148.   }
  149.  
  150.   /* copy second polygon */
  151.   for (l = (j + 1) % f2->numpoints; l != j; l = (l + 1) % f2->numpoints) {
  152.     if (l == (j + 1) % f2->numpoints && !keep1)
  153.       continue;
  154.     VectorCopy(f2->pts[l], newf->pts[newf->numpoints]);
  155.     newf->numpoints++;
  156.   }
  157.  
  158.   RecalcFace(newf);
  159.   /* mprintf("TryMerge: merged %d + %d to %d\n", f1->numpoints, f2->numpoints, newf->numpoints); */
  160.  
  161.   return newf;
  162. }
  163.  
  164. /*
  165.  * ===============
  166.  * MergeFaceToList
  167.  * ===============
  168.  */
  169. struct visfacet *MergeFaceToList(__memBase, struct visfacet *face, struct visfacet *list)
  170. {
  171.   struct visfacet *newf, *f;
  172.  
  173.   for (f = list; f; f = f->next) {
  174.     /* CheckColinear(f); */
  175.     if (mergedebug) {
  176.       Draw_ClearWindow();
  177.       Draw_DrawFace(face);
  178.       Draw_DrawFace(f);
  179.       Draw_SetBlack();
  180.     }
  181.     newf = TryMerge(bspMem, face, f);
  182.     if (!newf)
  183.       continue;
  184.     FreeFace(face);
  185.     f->numpoints = -1;                        /* merged out */
  186.  
  187.     return MergeFaceToList(bspMem, newf, list);
  188.   }
  189.  
  190.   /* didn't merge, so add at start */
  191.   face->next = list;
  192.   return face;
  193. }
  194.  
  195. /*
  196.  * ===============
  197.  * FreeMergeListScraps
  198.  * ===============
  199.  */
  200. struct visfacet *FreeMergeListScraps(struct visfacet *merged)
  201. {
  202.   struct visfacet *head, *next;
  203.  
  204.   head = NULL;
  205.   for (; merged; merged = next) {
  206.     next = merged->next;
  207.     if (merged->numpoints == -1)
  208.       FreeFace(merged);
  209.     else {
  210.       merged->next = head;
  211.       head = merged;
  212.     }
  213.   }
  214.  
  215.   return head;
  216. }
  217.  
  218. /*
  219.  * ===============
  220.  * MergePlaneFaces
  221.  * ===============
  222.  */
  223. void MergePlaneFaces(__memBase, struct surface *plane)
  224. {
  225.   struct visfacet *f1, *next;
  226.   struct visfacet *merged;
  227.  
  228.   merged = NULL;
  229.  
  230.   for (f1 = plane->faces; f1; f1 = next) {
  231.     next = f1->next;
  232.     merged = MergeFaceToList(bspMem, f1, merged);
  233.   }
  234.  
  235.   /* chain all of the non-empty faces to the plane */
  236.   plane->faces = FreeMergeListScraps(merged);
  237. }
  238.  
  239. /*
  240.  * ============
  241.  * MergeAll
  242.  * ============
  243.  */
  244. void MergeAll(__memBase, struct surface *surfhead)
  245. {
  246.   struct surface *surf;
  247.   int mergefaces, numsurf = 0, i;
  248.   struct visfacet *f;
  249.  
  250.   mprintf("----- MergeAll ----------\n");
  251.  
  252.   /* PROGRESS-ONLY! */
  253.   for (surf = surfhead; surf; surf = surf->next)
  254.     numsurf++;
  255.  
  256.   mergefaces = 0;
  257.   for (surf = surfhead, i = 0; surf; surf = surf->next, i++) {
  258.     MergePlaneFaces(bspMem, surf);
  259.     Draw_ClearWindow();
  260.     for (f = surf->faces; f; f = f->next) {
  261.       Draw_DrawFace(f);
  262.       mergefaces++;
  263.     }
  264.     mprogress(numsurf, i + 1);
  265.   }
  266.  
  267.   mprintf("%5i mergefaces\n", mergefaces);
  268. }
  269.